This invention is related to the field of communications security, and more particularly to a random sequence generator which may be used in maintaining communication security.
In systems where communications security is desired, it is common to encrypt or scramble the data to be transmitted, but the degree of security obtained is dependent upon the degree of difficulty encountered by an unauthorized user in determining the encryption key or the scrambling sequence employed. Thus, for secure communications, it is imperative that the encryption key or scrambling sequence have a high degree of randomness.
By classical definitions, a binary sequence is a random (looking) sequence if it satisfies the "randomness postulates" as presented by S. W. Golomb, Shift Sequences, Holden Day, San Francisco, 1967. It is well known that a sequence which satisfies the randomness postulates is not necessarily suitable for application in a secure system. The other desired properties for a good random sequence include the complexity of the sequence (defined according to some criteria) and problems related to its "invertibility," i.e., the complexity of computations required to find the "seed" from a block of output sequences assuming that the feedback function is known.
Thus, an essential component of many secure communications systems is the random sequence generator. Several techniques for the generation of random sequences are known with the simplest technique involving the use of a shift register with a linear or nonlinear feedback circuit. Non-linear feedback shift registers are more applicable and attractive for secure communications.
For a given m-stage shift register, about 2.sup.2m-1-m nonlinear feedback circuits exist such that the generated sequences satisfy the classical randomness postulates. Presently, there is no known general construction technique for designing a feedback function with reasonable complexity. Most of the analytical methods for constructing nonlinear sequences are based on concatenation of linear sequences, but it is not safe to use such sequences for security purposes.
A popular method for generating a nonlinear sequence is to apply a nonlinear function on a linear PN sequence, as shown in FIG. 1, This is commonly known as the Groth generator. In FIG. 1, the Linear Feedback Shift Register (LFSR) 10 generates a linear PN sequence, and the nonlinear function generator is schematically shown at 12. The main disadvantage of this technique is that an arbitrary choice of the nonlinear function generally does not lead to the generation of a sequence with desired randomness properties. Moreover, except for some special cases, e.g., as described by E. L. Key, "An Analysis of the Structure and Complexity of Non-linear Binary Sequence Generators," IEEE Transactions on Information Theory, November 1976, the complexity of the generated sequence has not been analyzed.
An alternative for generating nonlinear sequences is a sequence generator designed by Geffe and described in the above-cited reference by E. L. Key, Geffe's generator, illustrated in FIG. 2, consists of three linear feedback shift registers 14, 16 and 18, AND gates 20 and 22, with gate 22 having one inverted input 24, and a modulo-two adder (EXclusive-OR gate) 26. In this configuration the register 16 is used as a control register, to selectively connect the sequence from either the register 14 or the register 16, but not both, to the output via gate 26. If the present output from the controller register 16 is a logic 1, the output from register 14 is connected to gate 26 and to the sequence generator output. Otherwise, the output from register 18 becomes the sequence generator output.
The complexity of the sequence generator of FIG. 2, in terms of the number of stages of a linear feedback shift register which would exactly generate the same sequence, is equal to rs+(s+1)t, where r, s and t are the degree of primitive characteristic polynomials of shift registers 14, 16 and 18, respectively. The period of the output sequence is the least common multiple of 2.sup.r -1, 2.sup.s -1, and 2.sup.t -1.
The balanced distribution of zeros and ones at the output is the main advantage of the generator of FIG. 2. However, because of the involved linear terms, it is rather easy to find the "seed" from the output sequence. The complexity of the generator of FIG. 2 (Geffe's generator) can be increased by using Groth generators as the component registers. See the above-cited paper by E. L.. Key, as well as E. I.. Groth, "Generation of Binary Sequences with Controllable Complexity," IEEE Transaction on Information Theory, May 1971. In this case, however, the desired randomness properties are not guaranteed.